1. Field of the Invention
The present invention relates to resource management, in particular, but not exclusively in a transaction-based communication system wherein a number of requester elements are attempting to access a single resource.
2. Discussion of the Related Art
FIG. 1 shows an example of a routed transaction-based communication system which comprises a plurality of requester elements 2, 4, 6, 8 connected through an arbiter element 10 to a single resource 12. That is, in a transaction-based communication system each requester element supplies requests for accessing the single resource 12. Only one requester element can access the resource at any one time, and therefore the arbiter element 10 controls which requester element 2, 4, 6, 8 can have access to the resource. As shown in FIG. 2, each of the requester elements comprises a control unit 20 for generating requests and a buffer unit 22 having a plurality of storage locations for buffering the generated requests before these are sent on to the arbiter element 10.
Such a transaction-based communication system has many different potential applications. For example, one could consider that each of the requester elements represent different processing units in a computer system and are each competing to access a particular memory location (i.e. the resource 12) over a communication bus (managed by the arbiter element 10). FIG. 1A shows one such example of a computer 102 comprising a processor 100 that itself comprises a plurality of requester elements 2, 4, 6, 8 competing for a shared resource 12, and FIG. 1B shows another example of a computer 102 comprising a plurality of requester elements 2, 4, 6, 8 competing for a shared resource 12.
Another example, taken at a higher level, is if each of the requester elements is considered to be a client terminal that forms part of a client-server network wherein the resource 12 is the server terminal which the client terminals are trying to access over a communication network (involving arbiter 10). FIG. 1C shows one such example of a plurality of terminals 302, 304, 306, 308 competing to access a server 312. It will be appreciated that these are two very simple examples and that in practice the present invention can be applied to a variety of applications.
Each requester element 2, 4, 6, 8 is capable of performing a number of different tasks of varying priority. That is, a task having a high-priority needs to be serviced as soon as possible, whereas a task having a low-priority is not so urgent. In addition, some tasks may require a large number of accesses to the resource, but at a low-priority, whereas other tasks may require only a single access to the resource, but the access must be granted almost immediately.
Therefore, the control unit 20 which generates requests for each requester element 2, 4, 6, 8 provides some extra priority information along with the generated access request to indicate how urgent the request is. The arbiter element 10 can then use this priority information in its decision as to which request should be allowed to access the resource.
FIG. 2 shows the internal details of one of the requester elements 2, 4, 6, 8 as comprising a control unit 20 for generating requests which are stored in the buffer unit 22. The buffer unit 22 crosses the boundary indicated by the line 24 between two clock domains such that the clocks on either side of the buffer are unrelated and asynchronous. That is, the requests are clocked into the buffer under control of a first rate φ1 (related to the rate of the control unit 20) and are clocked out of the buffer under control of a second clock rate φ2 (related to the handling rate of the arbiter unit 10).
The buffer unit is able to store a number of requests which it then passes on to the arbiter element 10. The buffer unit 22 forwards on the requests to the arbiter in the same order in which it received them, that is on a first-in first-out (FIFO) basis.
However, the limitations of the circuit of FIG. 2 become apparent when one considers what happens when the control unit 20 generates a large number of low-priority access requests followed by a high-priority request. In this case, the buffer unit 22 of one of the requester elements, for example the second requester 4 of FIG. 1, will pass the first low-priority request to the arbiter 10, but this request may not be granted access to the resource if another requester element, for example the fourth requester 8, has a medium-priority request in progress. In fact, access may not be granted to the requester 4 for a long time, especially if other requesters 2, 6, 8 supply a continual stream of medium-priority transactions. This is not optimal since the requester 4 will have a high-priority request which is waiting at the back of the buffer unit.
Therefore, it is an aim of the embodiment of the present invention to manage high priority requests.
FIG. 3 shows a first known system which attempts to address this problem wherein the control unit 20 is shown to have direct control over a signal 28 which communicates the priority of the request to the arbiter element 10. For this system, as soon as the control unit 20 generates a high-priority transaction in the buffer unit 22, it raises the high-priority signal on line 28 to signal the arbiter to accept the request. However, the drawback of this system is that the control unit 20 does not have the visibility to check when the high-priority request has actually been read out of the buffer unit 22 and passed on to the arbiter element 10.
Therefore, it is difficult to decide exactly when to deassert the high-priority signal on line 28, since if the signal is disasserted too early then the high-priority request in the buffer unit 22 can be held up unnecessarily since the arbiter element 10 will not be aware that the high-priority request is still in the queue. On the other hand if the high-priority signal on line 28 is disasserted too late then other low-priority transactions will be given a high priority status which they do not require, allowing them access to the arbiter element 10 at the expense of other requester elements which might contain higher-priority requests.
FIG. 4 shows a second known system. A priority value 40 is placed into the buffer unit 22 along with the corresponding request. The buffer unit 22 also has a priority combiner 44 which continuously scans the priority value 40 corresponding to every request in the buffer and indicating a high-priority request to the arbiter element whenever there are any high-priority requests in the buffer. However, it can be seen from FIG. 4 that the memory structure of the buffer unit needs modification since a priority value needs to be stored along with the request itself. Because the priority combiner 44 requires direct access to the priority value 40 of every single request in the buffer unit 22, the priority value cannot be held in a standard memory or macro. Therefore, the priority value must be stored in separate flip-flops thereby increasing the silicon area requirement and the cost of the memory device.
A further disadvantage of the system shown in FIG. 4 is that the priority combiner 44 and the buffer unit 22 cross the two clock domains φ1, φ2, which introduces both synchronization and metastability issues which could result in some of the requests being allocated the wrong priority value.